import com.sun.org.apache.regexp.internal.RE;

import java.io.IOException;
import java.util.List;

public class TSP {
    public static void showSteps1(int D[][], List<Integer> steps, int start){
        int last=start;
        int sum=0;
        System.out.println("出发地\t---[距离]--->\t到达地");
        for (int step:steps){
            if (last==step) continue;
            System.out.println("  "+last+"\t\t----["+D[last][step]+"]---->\t  "+step);
            sum+=D[last][step];
            last=step;
        }

        sum+=D[last][start];
        System.out.println("  "+last+"\t\t----["+D[last][start]+"]---->\t  "+start);
        System.out.println("最佳路径距离："+sum);
    }
    public static void showSteps(int D[][], List<Integer> steps, int start){
        int last=start;
        int sum=0;

        System.out.println("详细输出：");
        System.out.print(0);
        for (int step:steps){
            if (last==step) continue;
            System.out.print("--["+D[last][step]+"]-->"+step);
            sum+=D[last][step];
            last=step;
        }

        sum+=D[last][start];
        System.out.println("--["+D[last][start]+"]-->0");
        System.out.println("简略输出：");
        for (int p:steps) System.out.print(p+",");
        System.out.println("\n最佳径距离："+sum);
    }
    public static void main(String[] args) {
        int N=10;
        int D[][]= {
                {0,2,22,8,10,5},
                {2,0,4 ,7,9 ,6},
                {22,4,0,2,11,12},
                {8 ,7,2,0,6 ,7},
                {10,9,11,6,0,3},
                {5, 6,12,7,3,0},
        };
        D=DataMaker.readDist("data2.txt",N);
//        try {
//            D=DataMaker.readData("data1.txt",N);
//        } catch (IOException e) {
//            e.printStackTrace();
//            return;
//        }
        int start=0;
        //贪心算法
//        Greedy greedy =new Greedy(D,N,3);
//        greedy.run();
//        BacktrackingCut backtracking =new BacktrackingCut(D,N,start);
//        showSteps(D,backtracking.run(),start);
        System.out.println("\n####################遗传####################");
        GA ga = new GA(30, N, 1000, 0.8f, 0.9f);
        ga.init(D);
        ga.solve();

        System.out.println("\n####################贪心####################");
        Greedy greedy =new Greedy(D,N,start);
        showSteps(D,greedy.run(),start);

        System.out.println("\n####################广度剪枝####################");
        Pruning pruning =new Pruning(D,N,start);
        showSteps(D,pruning.run(),start);

//        Greedy greedy =new Greedy(D,N,3);
//        greedy.run();
        System.out.println("\n####################回溯####################");
        BacktrackingCut backtracking =new BacktrackingCut(D,N,start);
        showSteps(D,backtracking.run(),start);
    }
}
